/**
 * 139. 单词拆分
 * https://leetcode-cn.com/problems/word-break/
 */

/**
 * @param {string} target
 * @param {string[]} words
 */
function exist(target, words) {
  let left = 0;
  let right = words.length - 1;
  let middle;
  while (left <= right) {
    middle = Math.floor((left + right) / 2);
    if (target === words[middle]) return true;
    if (target < words[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return false;
}

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function wordBreak(s, wordDict) {
  const src = [];
  wordDict.sort();
  let maxLength = 0;
  let length = 0;
  for (let i = 0; i < wordDict.length; i += 1) {
    const word = wordDict[i];
    length = word.length;
    const words = src[length] || [];
    words.push(word);
    src[length] = words;
    if (length > maxLength) maxLength = length;
  }
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  let minIndex;
  for (let i = 0; i < s.length; i += 1) {
    minIndex = Math.max(i - maxLength + 1, 0);
    for (let j = i; j >= minIndex; j -= 1) {
      const wordLength = i - j + 1;
      if (dp[j] && src[wordLength] && exist(s.substring(j, i + 1), src[wordLength])) {
        dp[i + 1] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak('applepenapple', ['apple', 'pen']) === true);
console.log(wordBreak('leetcode', ['leet', 'code']) === true);
console.log(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']) === false);
